Sekolah ini telah dibuka pada tahun 1961. Sebelum ini ia adalah sebahagian dari Sekolah Menengah Gajah Berang iaitu semenjak tahun 1959. Sewaktu mula-mula dibuka, bilangan murid-muridnya hanya seramai 414 orang dan semuanya terdiri daripada murid-murid perempuan. Pada ketika itu sekolah ini mempunyai dua bahasa pengantar iaitu Bahasa Malaysia dan Bahasa Inggeris. Walau bagaimanapun pada tahun 1965, bahagian yang berpengantar Bahasa Malaysia berpindah ke bangunan lain dan seterusnya bertukar nama menjadi Sekolah Menengah Tun Tijah. Sekolah Tinggi Perempuan ini dirasmikan oleh Yang Berhormat Menteri Pelajaran Persekutuan Tanah Melayu iaitu Encik Abdul Rahman bin Hj. Talib pada tahun 16 November 1962. Terdapat 11 bangunan pada awalnya iaitu pejabat sekolah, bilik guru, bilik darjah dan makmal sains. Tiga buah blok lagi dibina untuk dijadikan asrama. Terdapat sebuah padang yang terletak bersebelahan dewan sekolah, sebuah pusat sumber galeri seni dan galeri warisan. Aliran sains bermula dari awal tahun 70-an dan kini meningkat kepada 6 buah kelas. Jumlah kelas telah bertambah daripada 12 buah (1961) menjadi 39 buah yang terdiri Tingkatan 1 hingga Tingkatan 6 Atas (Januari 2007).

Aliran sastera pula telah diadakan lebih awal iaitu pada tahun 1959 (sejak di SMK Gajah Berang). Bilangan guru pada awalnya hanya seramai 29 orang dan bilangan pekerja hanya seramai 5 orang. Dahulu, sekolah ini dikenali sebagai Malacca Girls High School (MGHS) bersesuaian dengan penubuhanya yang dikhaskan kepada murid perempuan sahaja dari dahulu sehingga kini. bilangan murid daripada 414 orang (1961) kepada 1031 orang (Jun 2017). Manakala bilangan guru pula daripada 37 orang (1973) menjadi 90 orang (Jun 2017) dengan bilangan staf sokongan ialah seramai 20 orang serta penghuni asrama seramai 300 orang.

Pada tahun 2007, sekolah ini telah menerima Anugerah Sekolah Cemerlang dan seterusnya pada  tahun 2008, SMKTPM berdiri gah sebagai sebuah Sekolah Kluster Kecemerlangan (SKK) Gred A di daerah Melaka Tengah, Melaka. Mata pelajaran Seni Visual dan Pasukan Pancaragam dipilih sebagai bidang kebitaraan sekolah.